package com.sfx.算法专题.链表.双指针;

/**
 * Created with IntelliJ IDEA.
 * Description: 旋转链表
 * User: sfx
 * Date: 2023-07-30
 * Time: 15:45
 */
public class Code_3_rotateRight {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    static class Solution {
        public ListNode rotateRight(ListNode head, int k) {
            if(head ==null) return null;
            ListNode tmp = head;
            int cnt = 0;
            while(tmp != null) {
                tmp = tmp.next;
                cnt++;
            }
            //使用快慢指针
            ListNode fast = head;
            ListNode slow = head;
            k = k >= cnt ? (k%cnt) : k;
            if(k == 0) return head;
            //快指针先走k步
            while(k>0) {
                fast = fast.next;
                k--;
            }
            //快慢指针走到fast.next为null
            while(fast.next != null) {
                fast = fast.next;
                slow = slow.next;
            }
            ListNode slowNext = slow.next;
            slow.next = null;
            //找到链表的最后一个节点
            fast.next = head;
            return slowNext;
        }
    }
}